package leetcode_200;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;


/**
 *@author 周杨
 *PathSumII_113 给定一棵树和一个整数 判断有无根节点到叶子的路径 val和等于该整数 如果有 返回所有路径集合
 *describe:回溯法 89%
 *2018年5月21日 上午9:21:23
 */
public class PathSumII_113 {
	List<List<Integer>> res;
	public static void main(String[] args) {
		PathSumII_113 test=new PathSumII_113();
		//System.out.println(test.pathSum(root, sum));
	}
	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		this.res=new ArrayList<List<Integer>>();
        if(root==null)
        	return this.res;
        help(new ArrayList<Integer>(),root,sum);
        return this.res;
    }
	
	
	private void help(List<Integer> list,TreeNode root,int sum) {//保证每次只进入不空的节点
		list.add(root.val);
		if(root.left!=null) {
			help(list,root.left,sum-root.val);
		}
		if(root.right!=null)
			help(list,root.right,sum-root.val);
		if(root.left==null&&root.right==null&&sum-root.val==0) {
			List<Integer> now =new ArrayList<Integer>();
			now.addAll(list);
			this.res.add(now);
		}
		list.remove(root.val);
			
	}
	
}
